{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #The Time When the Network Becomes Idle"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #breadth-first-search #graph #array"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #广度优先搜索 #图 #数组"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: networkBecomesIdle"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #网络空闲的时刻"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你一个有 <code>n</code>&nbsp;个服务器的计算机网络，服务器编号为&nbsp;<code>0</code>&nbsp;到&nbsp;<code>n - 1</code>&nbsp;。同时给你一个二维整数数组&nbsp;<code>edges</code>&nbsp;，其中&nbsp;<code>edges[i] = [u<sub>i</sub>, v<sub>i</sub>]</code>&nbsp;表示服务器&nbsp;<code>u<sub>i</sub></code> 和&nbsp;<code>v<sub>i</sub></code><sub>&nbsp;</sub>之间有一条信息线路，在&nbsp;<strong>一秒</strong>&nbsp;内它们之间可以传输&nbsp;<strong>任意</strong>&nbsp;数目的信息。再给你一个长度为 <code>n</code>&nbsp;且下标从&nbsp;<strong>0</strong>&nbsp;开始的整数数组&nbsp;<code>patience</code>&nbsp;。</p>\n",
    "\n",
    "<p>题目保证所有服务器都是 <b>相通</b>&nbsp;的，也就是说一个信息从任意服务器出发，都可以通过这些信息线路直接或间接地到达任何其他服务器。</p>\n",
    "\n",
    "<p>编号为 <code>0</code>&nbsp;的服务器是 <strong>主</strong>&nbsp;服务器，其他服务器为 <strong>数据</strong>&nbsp;服务器。每个数据服务器都要向主服务器发送信息，并等待回复。信息在服务器之间按 <strong>最优</strong>&nbsp;线路传输，也就是说每个信息都会以 <strong>最少时间</strong>&nbsp;到达主服务器。主服务器会处理 <strong>所有</strong>&nbsp;新到达的信息并 <strong>立即</strong>&nbsp;按照每条信息来时的路线 <strong>反方向</strong> 发送回复信息。</p>\n",
    "\n",
    "<p>在 <code>0</code>&nbsp;秒的开始，所有数据服务器都会发送各自需要处理的信息。从第 <code>1</code>&nbsp;秒开始，<strong>每</strong>&nbsp;一秒最 <strong>开始</strong>&nbsp;时，每个数据服务器都会检查它是否收到了主服务器的回复信息（包括新发出信息的回复信息）：</p>\n",
    "\n",
    "<ul>\n",
    "\t<li>如果还没收到任何回复信息，那么该服务器会周期性&nbsp;<strong>重发</strong>&nbsp;信息。数据服务器&nbsp;<code>i</code>&nbsp;每&nbsp;<code>patience[i]</code>&nbsp;秒都会重发一条信息，也就是说，数据服务器&nbsp;<code>i</code>&nbsp;在上一次发送信息给主服务器后的 <code>patience[i]</code>&nbsp;秒 <strong>后</strong>&nbsp;会重发一条信息给主服务器。</li>\n",
    "\t<li>否则，该数据服务器&nbsp;<strong>不会重发</strong>&nbsp;信息。</li>\n",
    "</ul>\n",
    "\n",
    "<p>当没有任何信息在线路上传输或者到达某服务器时，该计算机网络变为 <strong>空闲</strong>&nbsp;状态。</p>\n",
    "\n",
    "<p>请返回计算机网络变为 <strong>空闲</strong>&nbsp;状态的&nbsp;<strong>最早秒数</strong>&nbsp;。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<p><img alt=\"example 1\" src=\"https://assets.leetcode.com/uploads/2021/09/22/quiet-place-example1.png\" style=\"width: 750px; height: 384px;\"></p>\n",
    "\n",
    "<pre><b>输入：</b>edges = [[0,1],[1,2]], patience = [0,2,1]\n",
    "<b>输出：</b>8\n",
    "<strong>解释：</strong>\n",
    "0 秒最开始时，\n",
    "- 数据服务器 1 给主服务器发出信息（用 1A 表示）。\n",
    "- 数据服务器 2 给主服务器发出信息（用 2A 表示）。\n",
    "\n",
    "1 秒时，\n",
    "- 信息 1A 到达主服务器，主服务器立刻处理信息 1A 并发出 1A 的回复信息。\n",
    "- 数据服务器 1 还没收到任何回复。距离上次发出信息过去了 1 秒（1 &lt; patience[1] = 2），所以不会重发信息。\n",
    "- 数据服务器 2 还没收到任何回复。距离上次发出信息过去了 1 秒（1 == patience[2] = 1），所以它重发一条信息（用 2B 表示）。\n",
    "\n",
    "2 秒时，\n",
    "- 回复信息 1A 到达服务器 1 ，服务器 1 不会再重发信息。\n",
    "- 信息 2A 到达主服务器，主服务器立刻处理信息 2A 并发出 2A 的回复信息。\n",
    "- 服务器 2 重发一条信息（用 2C 表示）。\n",
    "...\n",
    "4 秒时，\n",
    "- 回复信息 2A 到达服务器 2 ，服务器 2 不会再重发信息。\n",
    "...\n",
    "7 秒时，回复信息 2D 到达服务器 2 。\n",
    "\n",
    "从第 8 秒开始，不再有任何信息在服务器之间传输，也不再有信息到达服务器。\n",
    "所以第 8 秒是网络变空闲的最早时刻。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<p><img alt=\"example 2\" src=\"https://assets.leetcode.com/uploads/2021/09/04/network_a_quiet_place_2.png\" style=\"width: 100px; height: 85px;\"></p>\n",
    "\n",
    "<pre><b>输入：</b>edges = [[0,1],[0,2],[1,2]], patience = [0,10,10]\n",
    "<b>输出：</b>3\n",
    "<b>解释：</b>数据服务器 1 和 2 第 2 秒初收到回复信息。\n",
    "从第 3 秒开始，网络变空闲。\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>n == patience.length</code></li>\n",
    "\t<li><code>2 &lt;= n &lt;= 10<sup>5</sup></code></li>\n",
    "\t<li><code>patience[0] == 0</code></li>\n",
    "\t<li>对于&nbsp;<code>1 &lt;= i &lt; n</code> ，满足&nbsp;<code>1 &lt;= patience[i] &lt;= 10<sup>5</sup></code></li>\n",
    "\t<li><code>1 &lt;= edges.length &lt;= min(10<sup>5</sup>, n * (n - 1) / 2)</code></li>\n",
    "\t<li><code>edges[i].length == 2</code></li>\n",
    "\t<li><code>0 &lt;= u<sub>i</sub>, v<sub>i</sub> &lt; n</code></li>\n",
    "\t<li><code>u<sub>i</sub> != v<sub>i</sub></code></li>\n",
    "\t<li>不会有重边。</li>\n",
    "\t<li>每个服务器都直接或间接与别的服务器相连。</li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [the-time-when-the-network-becomes-idle](https://leetcode.cn/problems/the-time-when-the-network-becomes-idle/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [the-time-when-the-network-becomes-idle](https://leetcode.cn/problems/the-time-when-the-network-becomes-idle/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[[0,1],[1,2]]\\n[0,2,1]', '[[0,1],[0,2],[1,2]]\\n[0,10,10]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def networkBecomesIdle(self, edges: List[List[int]], patience: List[int]) -> int:\n",
    "        n = len(patience)\n",
    "        q = [(0, 0)]\n",
    "        dis = [-1] * n\n",
    "        dis[0] = 0\n",
    "        g = [[] for _ in range(n)]\n",
    "        for a, b in edges:\n",
    "            g[a].append(b)\n",
    "            g[b].append(a)\n",
    "        \n",
    "        q = [0]\n",
    "        ret = 0\n",
    "        while q:\n",
    "            tmp = q\n",
    "            q = []\n",
    "            for node in tmp:\n",
    "                d = dis[node]\n",
    "                for son in g[node]:\n",
    "                    if dis[son] == -1:\n",
    "                        dis[son] = d + 1\n",
    "                        q.append(son)\n",
    "                        \n",
    "                        if d * 2 + 2 <= patience[son]:\n",
    "                            ret = max(ret, dis[son] * 2 + 1)\n",
    "                        else:\n",
    "                            last = ((d + 1) * 2 - 1) // patience[son] * patience[son]\n",
    "                            ret = max(last + 2 * d + 3, ret)\n",
    "        return ret"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def networkBecomesIdle(self, edges: List[List[int]], patience: List[int]) -> int:\n",
    "        n = len(patience)\n",
    "        g = [[] for _ in range(n)]\n",
    "        for u, v in edges:\n",
    "            g[u].append(v)\n",
    "            g[v].append(u)\n",
    "\n",
    "        vis = [False] * n\n",
    "        vis[0] = True\n",
    "        q = deque([0])\n",
    "        ans, dist = 0, 1\n",
    "        while q:\n",
    "            for _ in range(len(q)):\n",
    "                u = q.popleft()\n",
    "                for v in g[u]:\n",
    "                    if vis[v]:\n",
    "                        continue\n",
    "                    vis[v] = True\n",
    "                    q.append(v)\n",
    "                    ans = max(ans, (dist * 2 - 1) // patience[v] * patience[v] + dist * 2 + 1)\n",
    "            dist += 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def networkBecomesIdle(self, edges: List[List[int]], patience: List[int]) -> int:\n",
    "        # bfs 获取每一个节点到主节点距离\n",
    "        # 同时去计算每个节点发送信息最后一次\n",
    "        n = len(patience)\n",
    "        g = [[] for _ in range(n)]\n",
    "        for x, y in edges:\n",
    "            g[x].append(y)\n",
    "            g[y].append(x)\n",
    "        vis = [False] * n\n",
    "        vis[0] = True\n",
    "        q = deque([0])\n",
    "        ans, dis = 0, 1\n",
    "        while q:\n",
    "            for _ in range(len(q)):\n",
    "                x = q.popleft()\n",
    "                for y in g[x]:\n",
    "                    if vis[y]:\n",
    "                        continue\n",
    "                    vis[y] = True\n",
    "                    q.append(y)\n",
    "                    ans = max(ans, (dis * 2 - 1) // patience[y] * patience[y] + dis * 2 + 1)\n",
    "            dis += 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def networkBecomesIdle(self, edges: List[List[int]], patience: List[int]) -> int:\n",
    "        from collections import deque\n",
    "        n = len(patience)\n",
    "        g = [[] for _ in range(n)]\n",
    "        \n",
    "        for e in edges:\n",
    "            v, w = e[0], e[1]\n",
    "            g[v].append(w)\n",
    "            g[w].append(v)\n",
    "        \n",
    "        vis = [False] * n\n",
    "        vis[0] = True\n",
    "        q = deque([0])\n",
    "        ans = 0\n",
    "        \n",
    "        for d in range(n):\n",
    "            tmp = q\n",
    "            q = deque()\n",
    "            \n",
    "            for v in tmp:\n",
    "                if v > 0:\n",
    "                    p = patience[v]\n",
    "                    t = p if 2 * d % p == 0 else 2 * d % p\n",
    "                    ans = max(ans, 4 * d - t + 1)\n",
    "                \n",
    "                for w in g[v]:\n",
    "                    if not vis[w]:\n",
    "                        vis[w] = True\n",
    "                        q.append(w)\n",
    "        \n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def networkBecomesIdle(self, edges: List[List[int]], patience: List[int]) -> int:\n",
    "        n = len(patience)\n",
    "        g = [[] for _ in range(n)]\n",
    "        for x, y in edges:\n",
    "            g[x].append(y)\n",
    "            g[y].append(x)\n",
    "        \n",
    "        def dijkstra(start):\n",
    "            dist = [inf] * n\n",
    "            dist[start] = 0\n",
    "\n",
    "            q = [(0, start)]\n",
    "\n",
    "            while q:\n",
    "                d, x = heappop(q)\n",
    "                for y in g[x]:\n",
    "                    if dist[y] > d + 1:\n",
    "                        dist[y] = d + 1\n",
    "                        q.append((dist[y], y))\n",
    "            return dist\n",
    "        \n",
    "        dist = dijkstra(0)\n",
    "\n",
    "        lastsend = [0] + [(i* 2 - 1) // p * p for i, p in zip(dist[1:], patience[1:])]\n",
    "        \n",
    "        ans = max(2 * i + j for i, j in zip(dist, lastsend)) + 1\n",
    "\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def networkBecomesIdle(self, edges: List[List[int]], patience: List[int]) -> int:\n",
    "        n = len(patience)\n",
    "        vis = [True] + [False] * (n-1)\n",
    "        graph = [[] for _ in range(n)]\n",
    "        for u, v in edges:\n",
    "            graph[u].append(v)\n",
    "            graph[v].append(u)\n",
    "        \n",
    "        dq = deque()\n",
    "        dq.append((0, 0))\n",
    "        ans = 0\n",
    "        while dq:\n",
    "            u, d = dq.popleft()\n",
    "            for v in graph[u]:\n",
    "                if not vis[v]:\n",
    "                    vis[v] = True\n",
    "                    ans = max(ans, 4 * d + 4 - ((2 * d + 1) % patience[v]))\n",
    "                    dq.append((v, d+1))\n",
    "        return ans\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def networkBecomesIdle(self, edges: List[List[int]], patience: List[int]) -> int:\n",
    "        n=len(patience)\n",
    "        g=[[] for i in range(n)]\n",
    "        for i in edges:\n",
    "            g[i[0]].append(i[1])\n",
    "            g[i[1]].append(i[0])\n",
    "\n",
    "        dis=[inf]*n\n",
    "        dis[0]=0\n",
    "        q=[(0,0)]\n",
    "        while q:\n",
    "            temp=heapq.heappop(q)\n",
    "            for i in g[temp[1]]:\n",
    "                if temp[0]+1<dis[i]:\n",
    "                    dis[i]=temp[0]+1\n",
    "                    heapq.heappush(q,(dis[i],i))\n",
    "                    # q.append((dis[i],i))\n",
    "\n",
    "        print(dis)\n",
    "        ans=0\n",
    "        for i in range(1,n):\n",
    "            ans=max(ans,dis[i]*2+(0 if patience[i]>=dis[i]*2 else (dis[i]*2-((dis[i]*2)%patience[i] if (dis[i]*2)%patience[i]!=0 else patience[i]))))\n",
    "\n",
    "\n",
    "        return ans+1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def networkBecomesIdle(self, edges: List[List[int]], patience: List[int]) -> int:\n",
    "        n=len(patience)\n",
    "        g=[[] for i in range(n)]\n",
    "        for i in edges:\n",
    "            g[i[0]].append(i[1])\n",
    "            g[i[1]].append(i[0])\n",
    "\n",
    "        dis=[inf]*n\n",
    "        q=[0]\n",
    "        dis[0]=0\n",
    "        step=-1\n",
    "        visited=set()\n",
    "        visited.add(0)\n",
    "        while q:\n",
    "            t=len(q)\n",
    "            step+=1\n",
    "            for i in range(t):\n",
    "                temp=q[i]\n",
    "                dis[temp]=step\n",
    "                for j in g[temp]:\n",
    "                    if j not in visited:\n",
    "                        visited.add(j)\n",
    "                        q.append(j)\n",
    "            q=q[t:]\n",
    "\n",
    "        print(dis)\n",
    "        ans=0\n",
    "        for i in range(n):\n",
    "            ans=max(ans,1+dis[i]*2+(0 if patience[i]>=dis[i]*2 else (dis[i]*2-((dis[i]*2)%patience[i] if (dis[i]*2)%patience[i]!=0 else patience[i]))))\n",
    "\n",
    "        return ans\n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def networkBecomesIdle(self, edges: List[List[int]], patience: List[int]) -> int:\n",
    "        n = len(patience)\n",
    "        g = collections.defaultdict(list)\n",
    "        for x, y in edges:\n",
    "            g[x].append(y)\n",
    "            g[y].append(x)\n",
    "        \n",
    "        time = [-1] * n\n",
    "        time[0] = 0\n",
    "        stack = [0]\n",
    "        while stack:\n",
    "            temp = []\n",
    "            for cur in stack:\n",
    "                for nex in g[cur]:\n",
    "                    if time[nex] == -1:\n",
    "                        time[nex] = time[cur] + 1\n",
    "                        temp.append(nex)\n",
    "            stack = temp\n",
    "        \n",
    "        return max((time[i] * 2 - 1) // patience[i] * patience[i] + time[i] * 2 for i in range(1, n)) + 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def networkBecomesIdle(self, edges: List[List[int]], patience: List[int]) -> int:\n",
    "        n = len(patience)\n",
    "        g = collections.defaultdict(list)\n",
    "        for x, y in edges:\n",
    "            g[x].append(y)\n",
    "            g[y].append(x)\n",
    "        \n",
    "        time = [-1] * n\n",
    "        time[0] = 0\n",
    "        stack = [0]\n",
    "        while stack:\n",
    "            temp = []\n",
    "            for cur in stack:\n",
    "                for nex in g[cur]:\n",
    "                    if time[nex] == -1:\n",
    "                        time[nex] = time[cur] + 1\n",
    "                        temp.append(nex)\n",
    "            stack = temp\n",
    "        \n",
    "        return max((time[i] * 2 - 1) // patience[i] * patience[i] + time[i] * 2 for i in range(1, n)) + 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def networkBecomesIdle(self, edges: List[List[int]], patience: List[int]) -> int:\n",
    "        n = len(patience)\n",
    "        g = collections.defaultdict(list)\n",
    "        for x, y in edges:\n",
    "            g[x].append(y)\n",
    "            g[y].append(x)\n",
    "        \n",
    "        time = [-1] * n\n",
    "        time[0] = 0\n",
    "        stack = [0]\n",
    "        while stack:\n",
    "            temp = []\n",
    "            for cur in stack:\n",
    "                for nex in g[cur]:\n",
    "                    if time[nex] == -1:\n",
    "                        time[nex] = time[cur] + 1\n",
    "                        temp.append(nex)\n",
    "            stack = temp\n",
    "        \n",
    "        return max((time[i] * 2 - 1) // patience[i] * patience[i] + time[i] * 2 for i in range(1, n)) + 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def networkBecomesIdle(self, edges: List[List[int]], patience: List[int]) -> int:\n",
    "        # 预处理\n",
    "        n = len(patience)\n",
    "        g = [[] for _ in range(n)]\n",
    "        for x,y in edges:\n",
    "            g[x].append(y)\n",
    "            g[y].append(x)\n",
    "        # BFS\n",
    "        q = [0]\n",
    "        seen = set()\n",
    "        seen.add(0)\n",
    "        d = 0\n",
    "        ans = 0\n",
    "        while q:\n",
    "            tmp = q\n",
    "            q = []\n",
    "            for x in tmp:\n",
    "                if x > 0:\n",
    "                    p = patience[x]\n",
    "                    t = p if 2*d % p==0 else 2*d%p\n",
    "                    ans = max(ans,4*d-t+1)\n",
    "                # 将x的儿子放入\n",
    "                for y in g[x]:\n",
    "                    if y not in seen:\n",
    "                        seen.add(y)\n",
    "                        q.append(y)\n",
    "            d += 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def networkBecomesIdle(self, edges: List[List[int]], patience: List[int]) -> int:\n",
    "        \n",
    "        n = len(patience)\n",
    "        g = [[] for _ in range(n)]\n",
    "        # 服务器之间连边\n",
    "        for x,y in edges:\n",
    "            g[x].append(y)\n",
    "            g[y].append(x)\n",
    "\n",
    "        vis = set()\n",
    "        vis.add(0)\n",
    "        q = [0]\n",
    "        ans = 0\n",
    "        d = 0\n",
    "        # BFS 广度优先搜索最近距离\n",
    "        while q:\n",
    "            tmp = q\n",
    "            q = []\n",
    "            for x in tmp:\n",
    "                # 更新答案\n",
    "                if x > 0:\n",
    "                    p = patience[x]\n",
    "                    t = p if 2 * d % p == 0 else 2 * d % p\n",
    "                    ans = max(ans, 4 * d - t + 1)\n",
    "                # 枚举儿子\n",
    "                for y in g[x]:\n",
    "                    if y not in vis:\n",
    "                        vis.add(y)\n",
    "                        q.append(y)\n",
    "            d += 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def networkBecomesIdle(self, edges: List[List[int]], patience: List[int]) -> int:\n",
    "        g = defaultdict(list)\n",
    "        for u, v in edges:\n",
    "            g[u].append(v)\n",
    "            g[v].append(u)\n",
    "        q = deque([0])\n",
    "        vis = {0}\n",
    "        ans = d = 0\n",
    "        while q:\n",
    "            d += 1\n",
    "            for _ in range(len(q)):\n",
    "                u = q.popleft()\n",
    "                for v in g[u]:\n",
    "                    if v not in vis:\n",
    "                        vis.add(v)\n",
    "                        q.append(v)\n",
    "                        t = d * 2\n",
    "                        ans = max(ans, (t - 1) // patience[v] * patience[v] + t + 1)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def networkBecomesIdle(self, edges: List[List[int]], patience: List[int]) -> int:\n",
    "        # 1-1、广度优先，找与0的最短路  建图（邻接表）\n",
    "        n = len(patience)\n",
    "        ges = [[] for _ in range(n)]\n",
    "        # return edges, patience\n",
    "        for u, v in edges:\n",
    "            ges[u].append(v)\n",
    "            ges[v].append(u)\n",
    "        # print(ges)\n",
    "        # 1-2、 单源最短路径  BFS\n",
    "        queue = deque([(0, 0)])\n",
    "        distance = [inf] * n\n",
    "        distance[0] = 0\n",
    "        while queue:\n",
    "            # print(queue)\n",
    "            server, cost = queue.popleft()\n",
    "            distance[server] = cost\n",
    "            # print(server, cost)\n",
    "            # print(distance)\n",
    "            for other in ges[server]:\n",
    "                # print('wc', other)\n",
    "                if distance[other] == inf:\n",
    "                    distance[other] = cost + 1\n",
    "                    # print(distance)\n",
    "                    queue.append((other, cost+1))\n",
    "                    # print('观察', queue)\n",
    "        # 计算部分\n",
    "        ans = 0\n",
    "        for i in range(n):\n",
    "            d = distance[i] * 2\n",
    "            p = patience[i]\n",
    "            ans = max(ans, (d-1)//p * p +d if p else 0)\n",
    "        return ans+1\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "        \n",
    "\n",
    "\n",
    "        # n = len(patience)\n",
    "        # g = [[] for _ in range(n)]\n",
    "        # for u, v in edges:\n",
    "        #     g[u].append(v)\n",
    "        #     g[v].append(u)\n",
    "\n",
    "        # vis = [False] * n\n",
    "        # vis[0] = True\n",
    "        # q = deque([0])\n",
    "        # ans, dist = 0, 1\n",
    "        # while q:\n",
    "        #     for _ in range(len(q)):\n",
    "        #         u = q.popleft()\n",
    "        #         for v in g[u]:\n",
    "        #             if vis[v]:\n",
    "        #                 continue\n",
    "        #             vis[v] = True\n",
    "        #             q.append(v)\n",
    "        #             ans = max(ans, (dist * 2 - 1) // patience[v] * patience[v] + dist * 2 + 1)\n",
    "        #     dist += 1\n",
    "        # return ans\n",
    "\n",
    "\n",
    "        # 单源最短路径\n",
    "        # dist = [0x7fffffff for _ in range(n)]\n",
    "        # dist[0] = 0\n",
    "        # st = deque([0])\n",
    "        # while st:\n",
    "        #     cur = st.popleft()\n",
    "        #     d = dist[cur] + 1\n",
    "        #     for nxt in g[cur]:\n",
    "        #         if d < dist[nxt]:\n",
    "        #             dist[nxt] = d\n",
    "        #             st.append(nxt)\n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def networkBecomesIdle(self, edges: List[List[int]], patience: List[int]) -> int:\n",
    "        # 1-1、广度优先，找与0的最短路  建图（邻接表）\n",
    "        n = len(patience)\n",
    "        ges = [[] for _ in range(n)]\n",
    "        # return edges, patience\n",
    "        for u, v in edges:\n",
    "            ges[u].append(v)\n",
    "            ges[v].append(u)\n",
    "        # print(ges)\n",
    "        # 1-2、 单源最短路径  BFS\n",
    "        queue = deque([(0, 0)])\n",
    "        distance = [inf] * n\n",
    "        distance[0] = 0\n",
    "        while queue:\n",
    "            # print(queue)\n",
    "            server, cost = queue.popleft()\n",
    "            distance[server] = cost\n",
    "            # print(server, cost)\n",
    "            # print(distance)\n",
    "            for other in ges[server]:\n",
    "                # print('wc', other)\n",
    "                if distance[other] == inf:\n",
    "                    distance[other] = cost + 1\n",
    "                    # print(distance)\n",
    "                    queue.append((other, cost+1))\n",
    "                    # print('观察', queue)\n",
    "        # 计算部分\n",
    "        ans = 0\n",
    "        for i in range(n):\n",
    "            d = distance[i] * 2\n",
    "            p = patience[i]\n",
    "            ans = max(ans, (d-1)//p * p +d if p else 0)\n",
    "        return ans+1\n",
    "\n",
    "\n",
    "\n",
    "        # n = len(patience)\n",
    "        # g = [[] for _ in range(n)]\n",
    "        # for u, v in edges:\n",
    "        #     g[u].append(v)\n",
    "        #     g[v].append(u)\n",
    "\n",
    "        # vis = [False] * n\n",
    "        # vis[0] = True\n",
    "        # q = deque([0])\n",
    "        # ans, dist = 0, 1\n",
    "        # while q:\n",
    "        #     for _ in range(len(q)):\n",
    "        #         u = q.popleft()\n",
    "        #         for v in g[u]:\n",
    "        #             if vis[v]:\n",
    "        #                 continue\n",
    "        #             vis[v] = True\n",
    "        #             q.append(v)\n",
    "        #             ans = max(ans, (dist * 2 - 1) // patience[v] * patience[v] + dist * 2 + 1)\n",
    "        #     dist += 1\n",
    "        # return ans\n",
    "\n",
    "\n",
    "        # 单源最短路径\n",
    "        # dist = [0x7fffffff for _ in range(n)]\n",
    "        # dist[0] = 0\n",
    "        # st = deque([0])\n",
    "        # while st:\n",
    "        #     cur = st.popleft()\n",
    "        #     d = dist[cur] + 1\n",
    "        #     for nxt in g[cur]:\n",
    "        #         if d < dist[nxt]:\n",
    "        #             dist[nxt] = d\n",
    "        #             st.append(nxt)\n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def networkBecomesIdle(self, edges: List[List[int]], patience: List[int]) -> int:\n",
    "        n = len(patience)\n",
    "        g = [[] for _ in range(n)]\n",
    "        for u,v in edges:\n",
    "            g[u].append(v)\n",
    "            g[v].append(u)\n",
    "        \n",
    "        q = [0]\n",
    "        level = 0\n",
    "        dist = [-1]*n\n",
    "        dist[0] = 0\n",
    "        level = 1\n",
    "        while q:\n",
    "            tmp = q[:]\n",
    "            q = []\n",
    "            for x in tmp:\n",
    "                for y in g[x]:\n",
    "                    if dist[y]==-1:\n",
    "                        dist[y] = level\n",
    "                        q.append(y)\n",
    "            level += 1\n",
    "\n",
    "        latest_time = -1\n",
    "        for i in range(1,n):\n",
    "            latest_time = max(latest_time, \\\n",
    "                ((dist[i]*2-1)//patience[i])*patience[i] + dist[i]*2 +1)\n",
    "        return latest_time"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def networkBecomesIdle(self, edges: List[List[int]], patience: List[int]) -> int:\n",
    "        g = defaultdict(list)\n",
    "        for u, v in edges:\n",
    "            g[u].append(v)\n",
    "            g[v].append(u)\n",
    "        q = deque([0])\n",
    "        vis = {0}\n",
    "        ans = d = 0\n",
    "        while q:\n",
    "            d += 1\n",
    "            t = d * 2\n",
    "            for _ in range(len(q)):\n",
    "                u = q.popleft()\n",
    "                for v in g[u]:\n",
    "                    if v not in vis:\n",
    "                        vis.add(v)\n",
    "                        q.append(v)\n",
    "                        ans = max(ans, (t - 1) // patience[v] * patience[v] + t + 1)\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def networkBecomesIdle(self, edges: List[List[int]], patience: List[int]) -> int:\n",
    "        n = len(patience)\n",
    "        dis = [0] + [-1] * (n-1)\n",
    "        graph = [[] for _ in range(n)]\n",
    "        for u, v in edges:\n",
    "            graph[u].append(v)\n",
    "            graph[v].append(u)\n",
    "        \n",
    "        dq = deque()\n",
    "        dq.append((0, 0))\n",
    "        while dq:\n",
    "            u, d = dq.popleft()\n",
    "            for v in graph[u]:\n",
    "                if dis[v] == -1:\n",
    "                    dis[v] = d + 1\n",
    "                    dq.append((v, d+1))\n",
    "        \n",
    "        ans = 0\n",
    "        patience[0] = 1\n",
    "        for d, p in zip(dis, patience):\n",
    "            ans = max(ans, 4 * d - ((2 * d - 1) % p))\n",
    "        return ans\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def networkBecomesIdle(self, edges: List[List[int]], patience: List[int]) -> int:\n",
    "        n = len(patience)\n",
    "        g = [[] for _ in range(n)]\n",
    "        for u, v in edges:\n",
    "            g[u].append(v)\n",
    "            g[v].append(u)\n",
    "\n",
    "        vis = [False] * n\n",
    "        vis[0] = True\n",
    "        q = deque([0])\n",
    "        ans, dist = 0, 1\n",
    "        while q:\n",
    "            for _ in range(len(q)):\n",
    "                u = q.popleft()\n",
    "                for v in g[u]:\n",
    "                    if vis[v]:\n",
    "                        continue\n",
    "                    vis[v] = True\n",
    "                    q.append(v)\n",
    "                    ans = max(ans, (dist * 2 - 1) // patience[v] * patience[v] + dist * 2 + 1)\n",
    "            dist += 1\n",
    "        return ans\n",
    "\n",
    "'''class Solution:\n",
    "    def networkBecomesIdle(self, edges: List[List[int]], patience: List[int]) -> int:\n",
    "        distance = [-1 for _ in range(0, len(patience))]\n",
    "        aa = dict()\n",
    "        for item in edges:\n",
    "            if item[0] in aa:\n",
    "                aa[item[0]].add(item[1])\n",
    "            else:\n",
    "                temp = set()\n",
    "                temp.add(item[1])\n",
    "                aa[item[0]] = temp\n",
    "\n",
    "        dis = 0\n",
    "        check_list = [0]\n",
    "        ans = 0\n",
    "\n",
    "        while(len(check_list) != 0):\n",
    "            temp_len = len(check_list)\n",
    "            for i in range(0, temp_len):\n",
    "                if distance[check_list[i]] != -1:\n",
    "                    continue\n",
    "                else:\n",
    "                    distance[check_list[i]] = dis\n",
    "                    if check_list[i] in aa:\n",
    "                        for item in aa[check_list[i]]:\n",
    "                            if distance[item] == -1:\n",
    "                                check_list.append(item)\n",
    "                    uhi = patience[check_list[i]]\n",
    "                    if uhi != 0:\n",
    "                        tmp = ((dis * 2 - 1) // uhi * uhi) + dis * 2\n",
    "                        ans = max(ans, tmp)\n",
    "            check_list = check_list[temp_len:]\n",
    "            dis += 1\n",
    "        return ans + 1'''\n",
    "                    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def networkBecomesIdle(self, edges: List[List[int]], patience: List[int]) -> int:\n",
    "        n = len(patience)\n",
    "        g = [[] for _ in range(n)]\n",
    "        for u, v in edges:\n",
    "            g[u].append(v)\n",
    "            g[v].append(u)\n",
    "\n",
    "        vis = [False] * n\n",
    "        vis[0] = True\n",
    "        q = deque([0])\n",
    "        ans, dist = 0, 1\n",
    "        while q:\n",
    "            for _ in range(len(q)):\n",
    "                u = q.popleft()\n",
    "                for v in g[u]:\n",
    "                    if vis[v]:\n",
    "                        continue\n",
    "                    vis[v] = True\n",
    "                    q.append(v)\n",
    "                    ans = max(ans, (dist * 2 - 1) // patience[v] * patience[v] + dist * 2 + 1)\n",
    "            dist += 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def networkBecomesIdle(self, edges: List[List[int]], patience: List[int]) -> int:\n",
    "        n = len(patience)\n",
    "        short = [0 for _ in range(n)]\n",
    "        edgeMatrix = defaultdict(list)\n",
    "        for each_edge in edges:\n",
    "            edgeMatrix[each_edge[0]].append(each_edge[1])\n",
    "            edgeMatrix[each_edge[1]].append(each_edge[0])\n",
    "        queue = deque([0])\n",
    "        step = 1\n",
    "        while len(queue) != 0:\n",
    "            for _ in range(len(queue)):\n",
    "                cn = queue.popleft()\n",
    "                for nn in edgeMatrix[cn]:\n",
    "                    if nn != 0 and short[nn] == 0:\n",
    "                        short[nn] = step\n",
    "                        queue.append(nn)\n",
    "            step += 1\n",
    "        print(short)\n",
    "        time = 0\n",
    "        for i in range(1, len(short)):\n",
    "            s, p = short[i] * 2, patience[i]\n",
    "            if s <= p: time = max(time, s + 1)\n",
    "            else:\n",
    "                if s % p == 0: time = max(time, ((s // p - 1)) * p + s + 1) \n",
    "                else: time = max(time, ((s // p)) * p + s + 1)\n",
    "        return time"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def networkBecomesIdle(self, es: List[List[int]], ps: List[int]) -> int:\n",
    "        # 求任一节点到root 的距离 并比较它的发信号周期 若2d <= p 则 2d 即可满足\n",
    "        # 否则离 2d 最近的 np 并 + 2d\n",
    "        # 求出所有的最大值\n",
    "        # 从root 开始 bfs\n",
    "        n = len(ps)\n",
    "        g = [[] for _ in range(n)]\n",
    "        for x, y in es:\n",
    "            g[x].append(y)\n",
    "            g[y].append(x)\n",
    "        dis = [0]*n\n",
    "        dis[0]=1\n",
    "        q = [0]\n",
    "        st = 1\n",
    "        while q:\n",
    "            p = []\n",
    "            for x in q:\n",
    "                for y in g[x]:\n",
    "                    if dis[y]==0:\n",
    "                        dis[y]= st\n",
    "                        p.append(y)\n",
    "            q = p\n",
    "            st+=1\n",
    "        ans = 0\n",
    "        for i in range(1, n):\n",
    "            d = 2*dis[i]\n",
    "            if ps[i] < 2*dis[i]:\n",
    "                d+= (2*dis[i] - 1)//ps[i] * ps[i]\n",
    "            ans = max(ans, d)\n",
    "        return ans +1\n",
    "\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import deque\n",
    "class Solution:\n",
    "    def networkBecomesIdle(self, edges: List[List[int]], patience: List[int]) -> int:\n",
    "        \n",
    "        n = len(patience)\n",
    "        g = [[] for _ in range(n)]\n",
    "        # 服务器之间连边\n",
    "        for v,w in edges:\n",
    "            g[v].append(w)\n",
    "            g[w].append(v)\n",
    "        # 把主服务器放入\n",
    "        vis = [False] * n\n",
    "        vis[0] = True\n",
    "        q = deque([0])\n",
    "        ans = 0\n",
    "        d = 0\n",
    "        while q:\n",
    "            tmp = q\n",
    "            q = []\n",
    "            for v in tmp:\n",
    "                if v > 0:\n",
    "                    p = patience[v]\n",
    "                    t = p if 2 * d % p == 0 else 2 * d % p\n",
    "                    ans = max(ans, 4 * d - t + 1)\n",
    "                \n",
    "                for w in g[v]:\n",
    "                    if not vis[w]:\n",
    "                        vis[w] = True\n",
    "                        q.append(w)\n",
    "            d += 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import deque\n",
    "class Solution:\n",
    "    def networkBecomesIdle(self, edges: List[List[int]], patience: List[int]) -> int:\n",
    "        n = len(patience)\n",
    "        g = [[] for _ in range(n)]\n",
    "        for u, v in edges:\n",
    "            g[u].append(v)\n",
    "            g[v].append(u)\n",
    "        visited = [0] * n\n",
    "        visited[0] = 1\n",
    "        q = deque()\n",
    "        q.append(0)\n",
    "        ans = 0\n",
    "        dist = 1\n",
    "        while q:\n",
    "            \n",
    "            for _ in range(len(q)):\n",
    "                u = q.popleft()\n",
    "                for v in g[u]:\n",
    "                    if visited[v] == 1:\n",
    "                        continue\n",
    "                    visited[v]=1\n",
    "                    ans = max(ans, 2 * dist + (2 * dist - 1)//patience[v] * patience[v] +1)\n",
    "                    q.append(v)\n",
    "            dist += 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def networkBecomesIdle(self, edges: List[List[int]], patience: List[int]) -> int:\n",
    "        n = len(patience)\n",
    "        g = [[] for _ in range(n)]\n",
    "        for e1, e2 in edges:\n",
    "            g[e1].append(e2)\n",
    "            g[e2].append(e1)\n",
    "        \n",
    "        d = [0] * n\n",
    "        q = [0]\n",
    "        h = 0\n",
    "        visit = set()\n",
    "        visit.add(0)\n",
    "        while q:\n",
    "            tmp = q\n",
    "            q = []\n",
    "            for qi in tmp:\n",
    "                d[qi] = h\n",
    "                for neqi in g[qi]:\n",
    "                    if neqi not in visit:\n",
    "                        visit.add(neqi)\n",
    "                        q.append(neqi)\n",
    "            h += 1\n",
    "        ans = 0\n",
    "        for i in range(1, n):\n",
    "            need = d[i] * 2 + (d[i] * 2 - 1) // patience[i] * patience[i]\n",
    "            if need > ans:\n",
    "                ans = need\n",
    "        return ans + 1\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def networkBecomesIdle(self, edges: List[List[int]], patience: List[int]) -> int:\n",
    "        n=len(patience)\n",
    "        g=defaultdict(list)\n",
    "        for x,y in edges:\n",
    "            g[x].append(y)\n",
    "            g[y].append(x)\n",
    "        dis=[n for _ in range (0,n)]\n",
    "        h=[]\n",
    "        dis[0]=0\n",
    "        heappush(h,[0,0])\n",
    "        while h:\n",
    "            d,x=heappop(h)\n",
    "            for j in g[x]:\n",
    "                if dis[j]>d+1:\n",
    "                    dis[j]=d+1\n",
    "                    heappush(h,[d+1,j])\n",
    "                else:\n",
    "                    continue\n",
    "        ans=0\n",
    "        for i in range (1,n):\n",
    "            if 2*dis[i]<=patience[i]:\n",
    "                ans=max(ans,2*dis[i])\n",
    "            else:\n",
    "                r=((2*dis[i]-1)//patience[i])*patience[i]\n",
    "                ans=max(ans,r+2*dis[i])\n",
    "        return ans+1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def networkBecomesIdle(self, edges: List[List[int]], patience: List[int]) -> int:\n",
    "        #首先要计算所有节点到0的距离，这个可以深度遍历edges来存储\n",
    "        n=len(patience)\n",
    "        distance=[-1 for i in range(n)]\n",
    "        D=dict(zip(range(n),[[] for _ in range(n)]))\n",
    "        for x,y in edges:\n",
    "            D[x].append(y)\n",
    "            D[y].append(x)\n",
    "        cur=deque([(0,0)])\n",
    "        while cur:\n",
    "            node,dist=cur.popleft()\n",
    "            #print(distance,node,dist)\n",
    "            if(distance[node]<0):\n",
    "                distance[node]=2*dist #来回时间\n",
    "                for next_node in D[node]:\n",
    "                    cur.append((next_node,dist+1))\n",
    "        res=0\n",
    "        for i in range(1,n):\n",
    "            dist,pati=distance[i],patience[i] \n",
    "            print(dist,pati)\n",
    "            res=max(res,2*dist-dist%pati+1 if dist%pati!=0 else 2*dist-pati+1) #如果dist%pati==0则向上取整到pati\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import deque, defaultdict\n",
    "from typing import List\n",
    "from math import inf\n",
    "\n",
    "class Solution:\n",
    "    def networkBecomesIdle(self, edges: List[List[int]], patience: List[int]) -> int:\n",
    "        n = len(patience)\n",
    "        distance = [inf] * n\n",
    "        graph = defaultdict(list)\n",
    "        for a, b in edges:\n",
    "            graph[a].append(b)\n",
    "            graph[b].append(a)\n",
    "        queue = deque([(0, 0)])\n",
    "        distance[0] = 0\n",
    "        while queue:\n",
    "            server, cost = queue.popleft()\n",
    "            distance[server] = cost\n",
    "            for other in graph[server]:\n",
    "                if distance[other] == inf:\n",
    "                    distance[other] = cost + 1\n",
    "                    queue.append((other, cost + 1))\n",
    "        ans = 0\n",
    "        for i in range(n):\n",
    "            d, p = distance[i] * 2, patience[i]\n",
    "            ans = max(ans, (d - 1) // p * p + d if p else 0)\n",
    "        return ans + 1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def networkBecomesIdle(self, edges: List[List[int]], patience: List[int]) -> int:\n",
    "        n = len(patience)\n",
    "        distance = [inf] * n\n",
    "        graph = defaultdict(list)\n",
    "        for a,b in edges:\n",
    "            graph[a].append(b)\n",
    "            graph[b].append(a)\n",
    "        queue = deque([(0,0)])\n",
    "        distance[0] = 0\n",
    "        while queue:\n",
    "            server, cost = queue.popleft()\n",
    "            distance[server] = cost\n",
    "            for other in graph[server]:\n",
    "                if distance[other] == inf:\n",
    "                    distance[other] = cost + 1\n",
    "                    queue.append((other, cost + 1))\n",
    "        ans = 0\n",
    "        for i in range(n):\n",
    "            d,p = distance[i] * 2, patience[i]\n",
    "            ans = max(ans,(d-1) // p * p + d if p else 0)\n",
    "        return ans + 1 "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def networkBecomesIdle(self, edges: List[List[int]], patience: List[int]) -> int:\n",
    "        n = len(patience)\n",
    "        g = [[] for _ in range(n)]\n",
    "\n",
    "        for x, y in edges:\n",
    "            g[x].append(y)\n",
    "            g[y].append(x)\n",
    "        \n",
    "        def dijkstra(start):\n",
    "            q = [(0, start)]\n",
    "            dis = [inf] * n\n",
    "            dis[start] = 0\n",
    "\n",
    "            while q:\n",
    "                d, x = heappop(q)\n",
    "                for y in g[x]:\n",
    "                    if dis[y] >= d + 1:\n",
    "                        dis[y] = d + 1\n",
    "                        heappush(q, (dis[y], y))\n",
    "            return dis\n",
    "        dis = dijkstra(0)\n",
    "\n",
    "        lastsend = [0] * n\n",
    "        for i, p in enumerate(patience):\n",
    "            if i == 0:\n",
    "                continue\n",
    "            lastsend[i] = (dis[i] * 2 - 1) // p * p\n",
    "        \n",
    "        return max([2* x + y for x, y in zip(dis, lastsend)]) +1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def networkBecomesIdle(self, edges: List[List[int]], patience: List[int]) -> int:\n",
    "        n = len(patience)\n",
    "        graph = {i: [] for i in range(n)}\n",
    "        for u, v in edges:\n",
    "            graph[u].append(v)\n",
    "            graph[v].append(u)\n",
    "        dis = [0] * n\n",
    "        queue = [0]\n",
    "        count = 0\n",
    "        visited = {0}\n",
    "        while queue:\n",
    "            count += 1\n",
    "            nxt = []\n",
    "            for u in queue:\n",
    "                for v in graph[u]:\n",
    "                    if v not in visited:\n",
    "                        visited.add(v)\n",
    "                        dis[v] = count\n",
    "                        nxt.append(v)\n",
    "            queue = nxt\n",
    "        ans = 0\n",
    "        for i in range(1, n):\n",
    "            back = 2 * dis[i]\n",
    "            t = back // patience[i]\n",
    "            if back % patience[i] == 0:\n",
    "                t -= 1\n",
    "            ans = max(ans, patience[i] * t + back)\n",
    "        return ans+1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def networkBecomesIdle(self, edges: List[List[int]], patience: List[int]) -> int:\n",
    "        n = len(patience)\n",
    "        g = [[] for _ in range(n)]\n",
    "\n",
    "        for x, y in edges:\n",
    "            g[x].append(y)\n",
    "            g[y].append(x)\n",
    "        \n",
    "        def dijkstra(start):\n",
    "            q = [(0, start)]\n",
    "\n",
    "            dis = [inf] * n\n",
    "            dis[start] = 0\n",
    "\n",
    "            while q:\n",
    "                d, x = heappop(q)\n",
    "                for y in g[x]:\n",
    "                    if dis[y] > d + 1:\n",
    "                        dis[y] = d + 1\n",
    "                        heappush(q, (dis[y], y))\n",
    "            return dis\n",
    "\n",
    "        dis = dijkstra(0)\n",
    "\n",
    "        lastsend = [0] * n\n",
    "        for i, p in enumerate(patience):\n",
    "            if i == 0:\n",
    "                continue\n",
    "            lastsend[i] = (dis[i] * 2 - 1) // p * p\n",
    "        \n",
    "        return max([2* x + y for x, y in zip(dis, lastsend)]) +1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def networkBecomesIdle(self, edges: List[List[int]], patience: List[int]) -> int:\n",
    "        n = len(patience)\n",
    "        g = [[] for _ in range(n)]\n",
    "\n",
    "        for x, y in edges:\n",
    "            g[x].append(y)\n",
    "            g[y].append(x)\n",
    "        \n",
    "        def dijkstra(start):\n",
    "            q = [(0, start)]\n",
    "            dis = [inf] * n\n",
    "            dis[start] = 0\n",
    "\n",
    "            while q:\n",
    "                d, x = heappop(q)\n",
    "                for y in g[x]:\n",
    "                    if dis[y] >= d + 1:\n",
    "                        dis[y] = d + 1\n",
    "                        heappush(q, (dis[y], y))\n",
    "            return dis\n",
    "        dis = dijkstra(0)\n",
    "\n",
    "        lastsend = [0] * n\n",
    "        for i, p in enumerate(patience):\n",
    "            if i == 0:\n",
    "                continue\n",
    "            lastsend[i] = 1 + (dis[i] * 2 - 1) // p * p\n",
    "        \n",
    "        return max([2* x + y for x, y in zip(dis, lastsend)]) "
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
